package zuoshen_video2.window;

import java.util.*;
import java.util.LinkedList;

import org.junit.Test;

public class WindowMax {

    // 滑动窗口最大值
    public int[] maxInWindow(int[] nums, int k) {
        int len = nums.length;
        int[] res = new int[len - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < k; i++) {
            if (deque.isEmpty() || nums[deque.peekLast()] > nums[i]) {
                deque.offerLast(i);
            } else {
                while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
            }
        }
        int idx = 0;
        for (int i = k; i < len; i++) {
            if (i - deque.peekFirst() > k - 1) {
                deque.pollFirst();
            }
            if (deque.isEmpty() || nums[deque.peekLast()] > nums[i]) {
                deque.offerLast(i);
            } else {
                while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
            }
            res[idx++] = nums[deque.peekFirst()];
        }
        return res;
    }

    public ArrayList<Integer> maxInWindows(int[] nums, int k) {
        int len = nums.length;
        if (k < 1 || k > len)
            return new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < k - 1; i++) {
            if (deque.isEmpty() || nums[deque.peekLast()] > nums[i]) {
                deque.offerLast(i);
            } else {
                while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
            }
        }
        for (int i = k - 1; i < len; i++) {
            if (!deque.isEmpty() && i - deque.peekFirst() > k - 1) {
                deque.pollFirst();
            }
            if (!deque.isEmpty() && deque.isEmpty() || !deque.isEmpty() && nums[deque.peekLast()] > nums[i]) {
                deque.offerLast(i);
            } else {
                while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
            }
            res.add(nums[deque.peekFirst()]);
        }
        return res;
    }

    @Test
    public void test1() {
        int[] nums = {10,14,12,11};
        
        System.out.println(maxInWindows(nums, 1));
    }

}

/*
 * 
 * 5 [10,14,12,11] 6 [14] 7 [] 8 []
 */
